This invention relates generally to communication protocols which are particularly suitable for self-reconfigurable multi-purpose communication networks, such as ad-hoc networks. More particularly, the protocol utilizes time-aware strategies and constraints to achieve routing objectives.
Various routing mechanisms have been proposed for ad-hoc networks. In general, an ad-hoc network has the following properties: (1) the structure of the network is unknown and may change dynamically, (2) each node has limited computation resources and lifetime, and (3) each node can obtain pieces of information from local sensors and communicate with others within a limited range. The power of such sensor networks is derived from communication, since each node is only able to sense local information with little computational resources. The routing mechanisms proposed for such networks fall into two basic categories, table-driven or source-initiated. Table-driven protocols rely on an underlying global routing table update mechanism for all nodes in the network, a mechanism that would not be energy efficient for ad-hoc dynamic networks. Source-initiated protocols, on the other hand, discover a route every time it is needed.
Existing routing protocols differ mainly in routing metrics, but all use a fixed routing objective. In most cases, routing objectives are implicitly embedded in strategies. Examples of these routing metrics include use of the shortest path, degree of association stability, signal stability or strength combined with shortest path, and information gain. Protocols also differ by destination specifications. The majority of early protocols are address-based or geographical location-based.
All existing routing protocols for wireless networks are implicitly associated with their routing strategies, which generally fall into two classes, flooding-based or search-based. Flooding-based methods begin with a route discovery phase (flooding the network), followed by a route maintenance phase for repairing disconnected routes. Flooding-based strategies are more suitable for relatively stable networks, since maintaining and repairing routes can be costly for dynamic networks. Search-based methods normally discover routes by selecting the next “best” hop at every node on the route. Routes may differ from message to message, even to the same destination node, and there is no route maintenance.
However, most real-time applications have firm real-time requirements. Messages in sensor networks need to arrive at certain destinations within bounded time while satisfying other route constraints and objectives. Some work has been done in Quality of Services (QoS) routing, in which routes are optimized according to required specifications, such as bounded time delay with load balancing. Most of the strategies in QoS are global-based, which is not suited for ad-hoc wireless sensor networks.
It would be useful to have a message specification mechanism that explicitly encodes the routing destinations, constraints and objectives in messages, so that generic-purpose instead of metric-specific routing strategies can be applied. Such a framework would permit the inclusion of a specification for time-bounded messages and a learning-based time-aware strategy which would dynamically change the weights between delay requirements and other objectives within an ad-hoc network.